package com.cty._04_Optimization._42_GreatestSumOfSubarrays;

/**
 * @Auther: cty
 * @Date: 2020/7/17 11:53
 * @Description: 面试题42：连续子数组的最大和
 * 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整
 * 数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * @version: 1.0
 */
public class GreatestSumOfSubarrays {

    public static int findGreatestSumOfSubarrays(int[] array, int length) {
        if(array==null || length<=0)
            return -1;

        int greatestSum = 0;
        int curSum = 0;
        for(int i=0; i<length; i++){
            if(curSum < 0)
                curSum = array[i];
            else
                curSum += array[i];

            if(curSum > greatestSum)
                greatestSum = curSum;
        }  // end for

        return greatestSum;
    }  // end findGreatestSumOfSubarrays()


}  // end class
